package com.leetcode.周赛.第236场;

/**
 * @author: xiaomi
 * @date: 2021/4/11
 * @description: 5728. 最少侧跳次数
 */
public class B_5728_最少侧跳次数 {
    static B_5728_最少侧跳次数 action = new B_5728_最少侧跳次数();

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    static void test1() {
        //
        int[] obstacles = new int[]{0, 1, 2, 3, 0};
        int res = action.minSideJumps(obstacles);

        System.out.println("res = " + res);
    }

    static void test2() {
        //

        //System.out.println("res = " + res);
    }

    static void test3() {
        //

        //System.out.println("res = " + res);
    }

    /**
     * 如果我在分析跳到哪个位置能让最后跳的次数最少，那么这是贪心；
     * 但是贪心肯定不如动态规划！
     *
     * @param obstacles
     * @return
     */
    public int minSideJumps(int[] obstacles) {
        int len = obstacles.length;
        int[][] dp = new int[4][len];
        dp[1][0] = 1;
        dp[2][0] = 0;
        dp[3][0] = 1;
        for (int i = 1; i < len; i++) {
            dp[obstacles[i]][i - 1] = -1;
            for (int j = 1; j < 4; j++) {
                if (j == obstacles[i]) {
                    dp[j][i] = -1;
                } else {
                    int min = len;
                    if (dp[j][i - 1] != -1) {
                        min = dp[j][i - 1];
                    }
                    if (j == 1) {
                        if (dp[2][i - 1] != -1) {
                            min = Math.min(dp[2][i - 1] + 1, min);
                        }
                        if (dp[3][i - 1] != -1) {
                            min = Math.min(dp[3][i - 1] + 1, min);
                        }
                    } else if (j == 2) {
                        if (dp[1][i - 1] != -1) {
                            min = Math.min(dp[1][i - 1] + 1, min);
                        }
                        if (dp[3][i - 1] != -1) {
                            min = Math.min(dp[3][i - 1] + 1, min);
                        }
                    } else {
                        if (dp[1][i - 1] != -1) {
                            min = Math.min(dp[1][i - 1] + 1, min);
                        }
                        if (dp[2][i - 1] != -1) {
                            min = Math.min(dp[2][i - 1] + 1, min);
                        }
                    }
                    dp[j][i] = min;
                }
            }
//            if (obstacles[i] == 0) {
//
//            } else {
//
//            }
        }
        int res = len;
        int endIndex = len - 1;
        for (int i = 1; i < 4; i++) {
            if (dp[i][endIndex] != -1) {
                res = Math.min(res, dp[i][endIndex]);
            }
        }
        return res;
    }
}
